# 描述
# 请写一个整数计算器，支持加减乘三种运算和括号。
#
# 数据范围：0\le |s| \le 1000≤∣s∣≤100，保证计算结果始终在整型范围内
#
# 要求：空间复杂度： O(n)O(n)，时间复杂度 O(n)O(n)
# 示例1
# 输入：
# "1+2"
# 复制
# 返回值：
# 3
# 复制
# 示例2
# 输入：
# "(2*(3-4))*5"
# 复制
# 返回值：
# -10
# 复制
# 示例3
# 输入：
# "3+2*3*4-1"
# 复制
# 返回值：
# 26
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
import re


class Solution:
    def solve(self, s: str) -> int:
        """
        1)一元表达式: +1, -15, => 直接计算
        2)二元表达式: 2+-3, 2*-3, 2*-3+1 => 优先用+-号拆分, 之后用*号拆分, 分别计算左右表达式然后根据中间的运算符计算
        3)带括号的表达式: 1*(2+-3)+1, (1+3)*(2+5)+1, (1+5) => 先计算括号内表达式

        :param s:
        :return:
        """
        if '(' in s:
            cnt_ = 0
            start_ = -1
            end_ = -1
            for i, each in enumerate(s):
                if each == '(':
                    cnt_ += 1
                    if cnt_ == 1:
                        start_ = i
                    elif cnt_ == 0 and start_ > -1:
                        end_ = i
                elif each == ')':
                    cnt_ -= 1
                    if cnt_ == 0 and start_ > -1:
                        end_ = i
                        break

            assert start_ > -1 and end_ > -1
            inner = self.solve(s[start_ + 1: end_])
            return self.solve(f'{s[:start_]}{inner}{s[end_ + 1:]}')

        # 判断是否是一元表达式
        match = re.match('^-?[0-9]+$', s)
        if match:
            return int(match.group(0))

        # 找出二元表达式的左右式, 二元表达式以+-法进行拆分, 注意符号不要拆分
        expression_before = False  # 上一个为表达式
        split_idx = -1
        for i, each in enumerate(s):
            if expression_before and (each == '+' or each == '-'):
                split_idx = i
            elif each == '*':
                assert expression_before
                if split_idx <0:
                    split_idx = i

            if each == '*' or each == '+' or each == '-':
                expression_before = False  # 对于下一个元素来说: 前面是运算符
            else:
                expression_before = True  # 对于下一个元素来说: 前面是表达式
        assert split_idx > 0, s
        if s[split_idx] == '+':
            return self.solve(s[:split_idx]) + self.solve(s[split_idx + 1:])
        elif s[split_idx] == '-':
            return self.solve(s[:split_idx]) - self.solve(s[split_idx + 1:])
        elif s[split_idx] == '*':
            return self.solve(s[:split_idx]) * self.solve(s[split_idx + 1:])
        else:
            raise ValueError(f'unexpected option: {s[split_idx]}')


solution = Solution()

assert solution.solve('-1350') == -1350
assert solution.solve('-2*-3+1') == eval('-2*-3+1')
assert solution.solve('-2*(-3+1)') == eval('-2*(-3+1)')
assert solution.solve('(5+2)-2*(-3+1)') == eval('(5+2)-2*(-3+1)')
assert solution.solve('(5+2)*2*(-3+1)') == eval('(5+2)*2*(-3+1)')
assert solution.solve('(2*(3-4*-2-9*3))*5') == eval('(2*(3-4*-2-9*3))*5')
assert solution.solve('1-2-3') == eval('1-2-3')

